闲话

这场只出了ABC,真参与的话估计又是不加不减的一个排名,D题说老实话感觉可以想出来,但是就没那个意识去那样解决这个问题,感觉还是见得有点少或者跟出题人心灵对不上.不过也是吸收到一种套路了.而且这场的话其实出了D就会使排名来到橙左右了,没出D可能就青啥也不加啥也不减那种.还是要多努力啊.

A. Choose Two Numbers

题目大意:给两个集合A和B,找出一种选取方式,在两个集合里各取一个数求和,并且新的和不在两个集合里出现过.

思路

显然直接暴力即可,数据范围很小.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[200],b[200];
int main()
{
	int n;scanf("%d",&n);
	set<int> sa,sb;
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]),sa.insert(a[i]);
    int m;scanf("%d",&m);
    for(int i = 1;i <= m;++i)	scanf("%d",&b[i]),sb.insert(b[i]);
    for(int i = 1;i <= n;++i)
    {
    	for(int j = 1;j <= m;++j)
    	{
    		int x = a[i] + b[j];
    		if(!sa.count(x) && !sb.count(x))
    		{
    			printf("%d %d",a[i],b[j]);
    			return 0;
    		}
    	}
    }
    return 0;
}

B. Make Product Equal One

题目大意:给你一个长度为$n$的序列,每次可以用$1$的代价把其中一个数减一或加一.求让整个序列的乘积结果是$1$的最小代价.
数据范围:
$1 \leq n \leq 10^5$
$-10^9 \leq a_i \leq 10^9$

思路

要使整个序列乘积为$1$显然要么全是$1$,要么存在偶数个$-1$.对每个数记录两个代价,一个是变成$1$一个是变成$-1$.分别看是哪种代价更小即可.如果一个数的负数代价是大于等于正数代价的,则还要额外维护一个差值,即正数代价减负数代价的最小值.当整个序列里变成$-1$的个数是奇数的时候,把结果加上之前维护的那个最小值,表示从这个序列里找出一个重新变成$1$的代价最小的之前变成$-1$的数的代价.
要注意等于也可以,以及防范爆int.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+7;
int a[N],u[N],d[N];
signed main()
{
	int n;scanf("%lld",&n);
	for(int i = 1;i <= n;++i)	scanf("%lld",&a[i]);
    int cnt = 0;
	for(int i = 1;i <= n;++i)	u[i] = abs(a[i] - 1),d[i] = abs(a[i] + 1);
	int revmin = 1e18;
	int res = 0;
	for(int i = 1;i <= n;++i)
	{
		if(u[i] >= d[i])
		{
			++cnt;
			revmin = min(u[i] - d[i],revmin);
			res += d[i];
		}	
		else res += u[i];
	}

	if(cnt % 2 == 0)	printf("%lld",res);
	else	printf("%lld",res + revmin);
    return 0;
}

C. Almost Equal

题目大意:给你一个整数$n$,现在要把$1$到$2n$这个排列里的所有的数按一定的顺序排成一个环,并且任意的连续$n$个元素组成的和之间的差值不能超过$1$.找出一种合法的构造方案,或者输出无解.
数据范围:
$1 \leq n \leq 10^5$

思路

看到数据范围这么大,多半是个结论题一遍就可以贪心出来.想到这个方向,再手推几个可以发现$n$是偶数的时候是无解的,是奇数的时候可能有某种构造方式.注意到样例其实是把1 3 5 2 4 6这个序列里3和5交换了一下,进一步尝试一下$n=5$的情况可以猜到这个题的结论就是先把奇偶数排出来,再每隔一个进行交换偶数部分和奇数部分对应的数.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5+7;
int res[N];
int main()
{
	int n;scanf("%d",&n);
	if(n % 2 == 0)	puts("NO");
	else
	{
		puts("YES");
		int cur = 1;
		for(int i = 1;i <= n;++i,cur += 2)	res[i] = cur;
		cur = 2;
		for(int i = n + 1;i <= 2 * n;++i,cur += 2)	res[i] = cur;
		for(int i = 2;i <= n - 1;i += 2)	swap(res[i],res[i + n]);
		for(int i = 1;i <= 2 * n;++i)	printf("%d ",res[i]);
	}
    return 0;
}

D. Shortest Cycle

题目大意:给你$n$个元素的序列,如果其中两个不同位置的元素满足a_i&a_j \neq 0则在$a_i$和$a_j$之间连一条无向边.现要求在这个图上求出一个长度最小的环,输出他的长度,或说明无解.

数据范围:
$1 \leq n \leq 10^5$
$0 \leq a_i \leq 10^{18}$

思路

关于最小环算法,有一个$floyd$找最小环的.但是这个题点数大的离谱,根本不可能跑的了$floyd$.但是数位比较小,有可能二进制位是真实的点进而找环.思路想到这里就断了.这个题难就难在第一步上.
下面说明一个结论:当$n \geq 128$时,整个图上一定存在着一个三元环.
首先如果把所有数的二进制数拆出来的话,那么只要某一个数位上存在三个$1$,那么就说明这三个元素是构成了一个三元环的.那么最多也才64位的数,在没$0$的前提下,如果有128位,你不管怎么操作,就假设它堆满好了,你必然会导致每个一个位置上出现有两个$1$,你再填一个数进去不可能避开任何一个位置,除非他是0.那么由于范围限制,实际上也不可能有64位,因此一旦到了128肯定就是有三元环的,那么剩下的情况就可以用$floyd$跑了,成功的把整个问题的规模缩减到了可以求解的范围.
floyd找最小环的代码就不讲了,模板题以后会专门写的.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200;
int g[N][N],d[N][N];
ll a[N];
int n,m,cnt;
signed main()
{
	scanf("%d",&n);
	memset(g,0x3f,sizeof g);
	for(int i = 1;i <= n;++i)
	{
		if(i >= 128)	break;
		scanf("%lld",&a[i]);
		if(!a[i])	--i,--n;
	}
	if(n >= 128)
	{
		puts("3");
		return 0;
	}
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			if((a[i] & a[j]) && i != j)	g[i][j] = 1;
			else g[i][j] = 0x3f3f3f3f;
	memcpy(d,g,sizeof g);
	ll res = 0x3f3f3f3f;
	for(int k = 1;k <= n;++k)
	{
		for(int i = 1;i < k;++i)
			for(int j = i + 1;j < k;++j)
				if((ll)d[i][j] + g[i][k] + g[k][j] < res)
					res = d[i][j] + g[i][k] + g[k][j];
			
		for(int i = 1;i <= n;++i)
			for(int j = 1;j <= n;++j)
				if(d[i][j] > d[i][k] + d[k][j])
					d[i][j] = d[i][k] + d[k][j];
	}
	if(res != 0x3f3f3f3f)	printf("%lld ",res);
	else puts("-1");
    return 0;
}